package leetcode.onehundred;

//141. 环形链表
public class HasCycle {

    //快慢指针
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    // 判断有无环，如果有就返回入口，没有返回null
    public ListNode detectCycle(ListNode head) {
        // 快慢指针移动，直到快指针到头
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            // 说明不存在环
            if (fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                ListNode pre = head;
                while (pre != slow) {
                    pre = pre.next;
                    slow = slow.next;
                }
                return pre;
            }
        }
        return null;

    }
}
